package com.code.leetcode.center50;

import javafx.util.Pair;

import java.util.*;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/7/29 21:13
 */
public class The127 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int L = beginWord.length();

        Map<String, List<String>> allComboDict = new HashMap<>();

        // 创造新的 word
        wordList.forEach((word) -> {
            for (int i = 0; i < word.length(); i++) {
                String newWord = word.substring(0, i) + "*" + word.substring(i + 1, L);
                List<String> list = allComboDict.getOrDefault(newWord, new ArrayList<>());
                list.add(word);
                allComboDict.put(newWord, list);
            }
        });

        Queue<Pair<String, Integer>> Q = new LinkedList<>();
        Q.add(new Pair<>(beginWord, 1));

        HashMap<String, Boolean> visited = new HashMap<>();
        visited.put(beginWord, true);

        while (!Q.isEmpty()) {
            Pair<String, Integer> node = Q.remove();
            String word = node.getKey();
            Integer level = node.getValue();
            for (int i = 0; i < L; i++) {
                String newWord = word.substring(0, i) + "*" + word.substring(i + 1, L);

                for (String adjacentWord : allComboDict.getOrDefault(newWord, new ArrayList<>())) {
                    if (adjacentWord.equals(endWord)) {
                        return level + 1;
                    }

                    if (!visited.containsKey(adjacentWord)) {
                        visited.put(adjacentWord, true);
                        Q.add(new Pair<>(adjacentWord, level + 1));
                    }
                }
            }
        }
        return 0;
    }
}
